package sort.cmp;

import sort.Sort;

import java.util.EmptyStackException;

/**
 * @Author: LDeng
 * @Date: 2021-03-26 8:45
 */
public class MergeSort<E extends Comparable<E>> extends Sort<E> {

    private E[] leftArray;

    @Override
    protected void sort() {
        //左边数组长度：即array.length>>1
        leftArray=(E[])new Comparable[(0+array.length)/2];
        //左边[0,mid), mid=(0+array.length)/2=array.length>>1
        //右边[mid,array.length)
        //组合起来的大数组[0,array.length)
        sort(0,array.length);
    }

    //对[begin，end)范围的数据进行归并排序
    private void sort(int begin,int end){
        if(end-begin<2) return;
        int mid=(begin+end)>>1;
        sort(begin,mid);
        sort(mid, end);
        merge(begin,mid,end);
    }

    //将[begin,mid)和[mid,end)范围的序列合并成一个有序序列
    private void merge(int begin,int mid,int end){
        //左边数组的索引
        int li=0;
        //左边数组结束索引
        int le=mid-begin;
        //右边数组索引
        int ri=mid;
        //右边数组结束索引
        int re=end;
        //大数组
        int ai=begin;
        //备份左边数组
        for (int i = li; i < le; i++) {
            leftArray[i]=array[begin+i];
        }
        //左边还没结束
        while (li<le){
            //数组右边取出来的值小于拷贝出来的左边的值
            if(ri<re && cmp(array[ri],leftArray[li])<0){//这里的ri<re 两个作用，
                                                        //一个防止数组越界
                                                        //另外右边先结束的时候，这个if条件不成立
                                                        //直接走到左边 把左边的元素搬到后面接个覆盖
                //右边数组中的值覆盖大数组中左边位置的值
                array[ai]=array[ri];
                ai++;
                ri++;
            }else{
                //左边数组的值覆盖大数组中左边位置的值
                array[ai]=leftArray[li];
                //左边数组指针向后移动
                li++;
                //大数组指针向后移动
                ai++;
            }
        }
    }
}
